package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

/**
 * 二叉搜索树转换为 累加树
 * 给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
 *
 * 提醒一下， 二叉搜索树 满足下列约束条件：
 *
 * 节点的左子树仅包含键 小于 节点键的节点。
 * 节点的右子树仅包含键 大于 节点键的节点。
 * 左右子树也必须是二叉搜索树。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution1038 {
    /**
     * 所谓 的累加树 就是当前节点加上右子树所有的值得总和
     * 依据 中序遍历的特点
     * 二叉树降序 然后 记录当前累加值
     *
     * @param root
     * @return
     */
    int sum = 0 ;
    public TreeNode bstToGst(TreeNode root) {
        if (root ==null) {
            return null;
        }
        bstToGst(root.right);
        // 当前节点的值等于 右边所有的值总和加上当前节点的值
        sum+= root.val;
        root.val = sum;
        bstToGst(root.left);
        return root;
    }

    /**
     * Morris 遍历 反向中序遍历
     *Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其反序中序遍历规则总结如下：
     *
     * 如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；
     *
     * 如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；
     *
     * 如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；
     *
     * 如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点；
     *
     * 重复步骤 1 和步骤 2，直到遍历结束。
     * @param root
     * @return
     */
    public TreeNode bstToGst01(TreeNode root) {

        TreeNode node = root;
        while (node!=null) {
            if (node.right == null) {
                sum+= node.val;
                root.val = sum;
                node = node.left;
            }else {

            }
        }
        return root;
    }
    public TreeNode getSuccessorNode(TreeNode treeNode){
        TreeNode right = treeNode.right;
        
        return null;
    }



}
